package leetcode.interviewClassics;

import leetcode.ListNode;

/**
 * @author Cheng Jun
 * Description: 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
 * @version 1.0
 * @date 2021/11/3 21:07
 */
public class getIntersectionNode {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(2, null);
        ListNode listNode0 = new ListNode(1, listNode1);

        ListNode listNode11 = new ListNode(2, listNode1);
        ListNode listNode01 = new ListNode(1, listNode11);
        System.out.println(getIntersectionNode(listNode0, listNode01));
    }

    // 肯定是要遍历 连个链表的所有节点的
    // 如果有交点，遍历到最后 肯定相等。逆否命题，不相等则肯定没交点
    // 如果有交点，怎么找到 交点开始的位置
    // 如果两个链表的长度相等，那么在有交点的情况下，依次比较每一个对应位置即可找到
    // 如果长度不相等，就考虑让较长链表先走几步，让断链表再走，走几步？相差几就先走几步。
    static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // 判断是否相交
        ListNode curA = headA;
        ListNode curB = headB;
        int lengthA = 0;
        int lengthB = 0;
        while (curA.next != null || curB.next != null) {
            if (curA.next != null) {
                curA = curA.next;
                lengthA++;
            }
            if (curB.next != null) {
                curB = curB.next;
                lengthB++;
            }
        }
        // 相交
        if (curA == curB) {
            // 长链表先走 Math.abs(lengthA - lengthB)
            int k = lengthA - lengthB;
            if (k >= 0) {
                return getIntersectionNode(headA, headB, k);
            } else {
                return getIntersectionNode(headB, headA, -k);
            }
        } else {
            return null;
        }
    }

    static ListNode getIntersectionNode(ListNode longListNode, ListNode shortListNode, int k) {
        ListNode curA = longListNode;
        ListNode curB = shortListNode;
        int counter = 0;
        while (true) {
            if (curA == curB) return curA;
            curA = curA.next;
            // 大于 k ，表明长链表已经走过了 k 步
            if (++counter > k) curB = curB.next;
        }
    }

    // A + B  = B + A
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        //tempA和tempB我们可以认为是A,B两个指针
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            //如果指针tempA不为空，tempA就往后移一步。
            //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
            tempA = tempA == null ? headB : tempA.next;
            //指针tempB同上
            tempB = tempB == null ? headA : tempB.next;
        }
        //tempA要么是空，要么是两链表的交点
        return tempA;
    }

}
